package graph;

import geocoding.ALGOTrip;
import geocoding.BusNetTrip;
import geocoding.LineTripStop;
import geocoding.TripStop;
import geocoding.TripStopComparator;

import java.io.FileWriter;
import java.io.IOException;
import java.sql.Timestamp;
import java.util.Calendar;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.LinkedList;



import org.jdesktop.application.Application;



public class PTAStarGraph extends SearchableGraph {
	 /**
     * implementation of the AStar algorithm for computing routes in the
     * bus network
     */
    
	private double [] bestCostSoFarInNode;
	private ChangeAStarGraph relaxedGraph;
	private int maxConnections;
	private FileWriter fw;
	private ALGOTrip relaxedSolution;
	private BusNetTrip currentSolution;
	
	public static double gw = 1, 
						 hw = 1,
						 c = 0;
	
	public PTAStarGraph() {
		super();
		relaxedGraph = new ChangeAStarGraph();
	}

	public void init() {
		computeMaxConnectionsForBusStop();
		computeDirectConnections();
	}
	
	private void computeMaxConnectionsForBusStop() {
		maxConnections = 0;
		Enumeration<ALGONode> busStops = nodes.elements();
		
		while (busStops.hasMoreElements()) {
			ALGONode n = busStops.nextElement();
			LinkedList<ALGOEdge> connections = edges.get(n.getNodeID());
			if ((connections != null) && (connections.size() > maxConnections)) maxConnections = 2*connections.size();
		}
	}
	
	private void computeDirectConnections() {
		Enumeration<ALGONode> nodeList = nodes.elements();
		Hashtable<String,ALGOPlacemarkNode> stopsAtSamePlace = new Hashtable<String, ALGOPlacemarkNode>();
		
		try {
			fw = new FileWriter("connections.log");
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		/* copy nodes to relaxed graph */
		
		while (nodeList.hasMoreElements()) {
			ALGOPlacemarkNode p = (ALGOPlacemarkNode)nodeList.nextElement();
			ALGOBusNetNode n;
			LinkedList<ALGOEdge> connections = edges.get(p.getNodeID());
			double connNum;
			String [] nameComps = p.getValue().getName().split(": ");
			
			relaxedGraph.addNode(n = new ALGOBusNetNode(p.getNodeID(), p.getValue()));
				
			if (stopsAtSamePlace.containsKey(nameComps[1])) {
				ALGOPlacemarkNode s = stopsAtSamePlace.get(nameComps[1]);
				LinkedList<ALGOEdge> sConnections = edges.get(s.getNodeID());
				
				if (connections != null) connNum = connections.size();
				else connNum = 0.0;
				if (sConnections != null) connNum += sConnections.size();
				
				relaxedGraph.addEdge(new ALGOBusChangeEdge(s.getNodeID(), p.getNodeID(), 0.5));
				relaxedGraph.addEdge(new ALGOBusChangeEdge(p.getNodeID(), s.getNodeID(), 0.5));
				
				n.setNodeCosts(1.0-Math.exp(-connNum/maxConnections-1.0));
				
				// update the importance weight of the bus stop already stored 
				// in the table
				
				n = (ALGOBusNetNode)relaxedGraph.getNode(s.getNodeID());
				n.setNodeCosts(1.0-Math.exp(-connNum/maxConnections-1.0));				
			}
			else {
				stopsAtSamePlace.put(nameComps[1], p);
				
				if (connections != null) {
					connNum = connections.size();
		
					n.setNodeCosts(1.0-Math.exp(-connNum/maxConnections-1.0));
				}
				else n.setNodeCosts(Math.exp(1.0));
			}
			
			// n.setNodeCosts(0.0);
			try {
				fw.write(n.getValue().getName() + ": " + n.getNodeCosts() + "\n");
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		/* compute graph for minimal change heuristic */
		
		nodeList = nodes.elements();
		
		while (nodeList.hasMoreElements()) {
			ALGOPlacemarkNode start = (ALGOPlacemarkNode)nodeList.nextElement();
			ALGOEdge [] edges = this.getEdgesForNode(start.getNodeID());
			if (edges != null) {
				for (int i = 0; i < edges.length; i++) {
					computeConnectionFromLine(start, start, ((ALGOBuslineEdge)edges[i]).getBusline(), 0.0);
					resetNodes();
				}
			}
		}
		
		try {
			fw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	private void computeConnectionFromLine(ALGOPlacemarkNode start, ALGOPlacemarkNode current, String line, double cost) {
		ALGOEdge [] edges = this.getEdgesForNode(current.getNodeID());
		if (edges == null) return;
		
		for (int i = 0; i < edges.length; i++) {
			ALGOBuslineEdge e = (ALGOBuslineEdge)edges[i];
			
			if (e.getBusline().equals(line)) {
				ALGOPlacemarkNode dest = (ALGOPlacemarkNode)this.getNode(e.getSink());
				if (!dest.isClosed()) {
					ALGOBusNetEdge bne;
					dest.putOnClosedList();
					
					try {
						fw.write(line + ": " + start.getValue().getName() + " -> " +
						         dest.getValue().getName() + ": " + (cost + e.getCosts()));
						fw.write("\n");
					} catch (IOException e1) {
						// TODO Auto-generated catch block
						e1.printStackTrace();
					}
					
					relaxedGraph.addEdge(bne = new ALGOBusNetEdge(start.getNodeID(), dest.getNodeID(), 1, line));
					bne.setMaxDuration(cost + e.getMaxDuration());

					computeConnectionFromLine(start, dest, line, cost + e.getCosts());
				}
			}
		}
	}
	
	private ALGOTrip computeH(ALGOPlacemarkNode startNode, ALGOPlacemarkNode targetNode) {
		int changes = 0;
		ALGOTrip result;
		
		relaxedGraph.setMaxConnections(maxConnections);
		relaxedGraph.initSearch(relaxedGraph.getNode(startNode.getNodeID()),
							    relaxedGraph.getNode(targetNode.getNodeID()));
		
		while (!relaxedGraph.solutionFound() && !relaxedGraph.noSolution()) {
			relaxedGraph.nextStep();
		}
		
		if (relaxedGraph.solutionFound()) {
			result = new ALGOTrip();
			
			double duration = 0.0;
			ALGOTrip path = relaxedGraph.computeShortestPath(relaxedGraph.getNode(startNode.getNodeID()),
				    relaxedGraph.getNode(targetNode.getNodeID()));
        	
    		for (int i = 0; i < path.size(); i++) {
    			ALGOEdge e = path.get(i);
    			
        		if (e instanceof ALGOBusNetEdge) {
            		result.appendPart((ALGOBusNetEdge)e);
        			System.out.println(((ALGOBusNetNode)relaxedGraph.getNode(e.getSource())).getValue().getName() +
        				           " -> " +
        				           ((ALGOBusNetNode)relaxedGraph.getNode(e.getSink())).getValue().getName() +
        				           ": " +
        				           ((ALGOBusNetEdge)e).getBusline());
        			
        			if (i < path.size()) changes ++;
        			duration = ((ALGOBusNetEdge) e).getMaxDuration();
        		}
        		else {
        			result.appendPart(new ALGOBusChangeEdge(e.getSource(), e.getSink()));
            		System.out.println(((ALGOBusNetNode)relaxedGraph.getNode(e.getSource())).getValue().getName() +
 				           " -> " +
 				           ((ALGOBusNetNode)relaxedGraph.getNode(e.getSink())).getValue().getName() +
 				           ": by foot");
            		duration = ((ALGOBusChangeEdge) e).getMaxDuration();
        		}
    		}
    		
    		System.out.println("Anzahl Umstiege: " + changes + ", Dauer: " + duration);
    		
    		return result;
		}
		else return null;
	}
	
	public void initSearch(ALGONode startNode, ALGONode targetNode) {
		Calendar now = Calendar.getInstance();
		ALGOEdge tripStep, tripConnection;
		ALGOBusNetNode sink;
		int [] depTime = new int[3];
		
		depTime[0] = now.get(Calendar.HOUR_OF_DAY);
		depTime[1] = now.get(Calendar.MINUTE);
		depTime[2] = now.get(Calendar.SECOND);
		
		agenda = new ALGOHeap(nodes.size());
		bestCostSoFarInNode = new double[nodes.size()];
		
		relaxedSolution = computeH((ALGOPlacemarkNode)startNode, (ALGOPlacemarkNode)targetNode);		
		tripStep = relaxedSolution.getNextStep();
		sink = (ALGOBusNetNode)relaxedGraph.getNode(tripStep.getSink());
		
		if (tripStep instanceof ALGOBusNetEdge) {
			tripConnection = this.getEdgeByLine(tripStep.getSource(), ((ALGOBusNetEdge)tripStep).getBusline());
			TripStop [] tripStops = ((ALGOBuslineEdge)tripConnection).findNextTrips(1, depTime);
			
			for (TripStop t : tripStops) {
				BusNetTrip bnt = new BusNetTrip();
				
				System.out.println(now.get(Calendar.HOUR_OF_DAY) + ":" + now.get(Calendar.MINUTE) + ":" + now.get(Calendar.SECOND) + " - next trip starts at: " + t.getStopTime());
				System.out.println("duration: " + ((ALGOBusNetEdge)tripStep).getMaxDuration() + " to arrive at: " + sink.getValue().getName());
				System.out.println("bus departs at " + t.getStopTime() + ", takes " + ((ALGOBusNetEdge)tripStep).getMaxDuration());
				bnt.add(new LineTripStop(t.getStopId(),
						                 t.getStopTime(),
						                 (int)((ALGOBusNetEdge)tripStep).getMaxDuration(),
						                 ((ALGOBuslineEdge)tripConnection).getBusline(),
						                 sink));
				agenda.insert(new ALGOTripHeapData(bnt,
						                           TripStopComparator.addInSeconds(0, 0, (int)((ALGOBusNetEdge)tripStep).getMaxDuration(), t),
						                           TripStopComparator.addInSeconds(0, 0, (int)((ALGOBusNetEdge)tripStep).getMaxDuration(), t)));
			}

			sink.putOnOpenList(agenda);				
		}
		else if (tripStep instanceof ALGOBusChangeEdge) {
			BusNetTrip bnt = new BusNetTrip();
			bnt.add(new LineTripStop(0,
					                 now.get(Calendar.HOUR_OF_DAY) + ":" + now.get(Calendar.MINUTE) + ":" + now.get(Calendar.SECOND),
					                 (int)ALGOBusChangeEdge.CHANGETIME,
					                 "by foot",
					                 sink));
			agenda.insert(new ALGOTripHeapData(bnt,
											   (depTime[0]*60+depTime[1])*60+depTime[2]+ALGOBusChangeEdge.CHANGETIME,
											   (depTime[0]*60+depTime[1])*60+depTime[2]+ALGOBusChangeEdge.CHANGETIME));
			sink.putOnOpenList(agenda);
		}
		
		for (int i = 0; i < nodes.size(); i++) {
    		LinkedList<ALGOEdge> l = edges.get(new Integer(i));
    		if (l != null) {
    			for(int j = 0; j < l.size(); j++) {
    				ALGOEdge e = l.get(j);
    				e.setOptimal(false);
    			}
    		}
		}
		
		
		currentNode = startNode;
		this.targetNode = targetNode;
	}
	
	public boolean solutionFound() {
		return (currentNode.getNodeID() == targetNode.getNodeID());
	}
	
	public boolean noSolution() {
		return agenda.isEmpty();
	}
	
	public void nextStep() {	
	 	ALGOTripHeapData hd;
    	BusNetTrip min;
    	LineTripStop lts;
    	double currentF = Double.MAX_VALUE;
    	ALGOEdge tripStep;
    	ALGOBusNetNode sink;
    	Hashtable<Integer, ALGOBusNetNode> toPutOnOpen = new Hashtable<Integer, ALGOBusNetNode>();
    	int [] depTime = new int[3];
    	
    	hd = (ALGOTripHeapData)agenda.retrieve();
    	agenda.deleteHighest();
    	
    	min = hd.getData();
    	lts = (LineTripStop)min.getLast();
    	currentNode = lts.getDest();
    	depTime = TripStopComparator.secondsToArray((int)hd.getActualCosts());
    	
    	System.out.println(lts.getDest().getNodeID() + ": will arrive at " + lts.getDest().getValue().getName() + " at " + depTime[0] + ":" + depTime[1] + ":" + depTime[2] + " (target: " + targetNode.getNodeID() + ")");
    	if (lts.getDest().getNodeID() == targetNode.getNodeID()) {
    		currentSolution = min;
    		return;
    	}

    	tripStep = relaxedSolution.getNextStep();
		sink = (ALGOBusNetNode)relaxedGraph.getNode(tripStep.getSink());

		if (tripStep instanceof ALGOBusNetEdge) {
			ALGOBuslineEdge tripConnection = (ALGOBuslineEdge)this.getEdgeByLine(tripStep.getSource(),
					                                                             ((ALGOBusNetEdge)tripStep).getBusline());
			TripStop [] tripStops = ((ALGOBuslineEdge)tripConnection).findNextTrips(1, TripStopComparator.secondsToArray((int)hd.getActualCosts()));
			
			for (TripStop t : tripStops) {
				BusNetTrip bnt = hd.getData().clone();
				
				System.out.println("duration: " + ((ALGOBusNetEdge)tripStep).getMaxDuration() + " to arrive at: " + sink.getValue().getName());
				System.out.println("bus departs at " + t.getStopTime() + ", takes " + ((ALGOBusNetEdge)tripStep).getMaxDuration());
				bnt.add(new LineTripStop(t.getStopId(),
						                 t.getStopTime(),
						                 (int)((ALGOBusNetEdge)tripStep).getMaxDuration(),
						                 ((ALGOBuslineEdge)tripConnection).getBusline(),
						                 sink));
				
				currentF = TripStopComparator.addInSeconds(0, 0, (int)((ALGOBusNetEdge)tripStep).getMaxDuration(), t);
				agenda.insert(new ALGOTripHeapData(bnt, currentF, currentF));
			}
		}
		else if (tripStep instanceof ALGOBusChangeEdge) {
			BusNetTrip bnt = hd.getData().clone();
			
			System.out.println("go by foot to " + sink.getValue().getName());
			bnt.add(new LineTripStop(0,
					                 depTime[0] + ":" + depTime[1] + ":" + depTime[2],
					                 (int)ALGOBusChangeEdge.CHANGETIME,
					                 "by foot",
					                 sink));
			
			currentF = (depTime[0]*60+depTime[1]+ALGOBusChangeEdge.CHANGETIME)*60+depTime[2];
			agenda.insert(new ALGOTripHeapData(bnt, currentF, currentF));
		}
		
		if (!sink.isOpen() && !sink.isClosed()) {
			// noch nicht besucht und auch bisher noch kein Kandidat dafür
			// succ wird Kandidat f�r weitere Suche

			toPutOnOpen.put(sink.getNodeID(), sink);
			bestCostSoFarInNode[sink.getNodeID()] = currentF;
		}
		else if (currentF < bestCostSoFarInNode[sink.getNodeID()]) {
			// succ schon besucht oder bereits Kandidat und besserer Weg zu succ als bisher
			// dann speichere diesen Pfad

			bestCostSoFarInNode[sink.getNodeID()] = currentF;

			if (sink.isClosed()) {
				sink.removeFromClosedList();

				// succ sogar schon besucht, nicht nur Kandidat
				// dann prüfe noch mal alles ab succ (backtracking)
			}

			toPutOnOpen.put(sink.getNodeID(), sink);
		}
		
		Enumeration<ALGOBusNetNode> onOpenEnum = toPutOnOpen.elements();
		while (onOpenEnum.hasMoreElements()) {
			onOpenEnum.nextElement().putOnOpenList(agenda);
			/*
		    	for (int i = 0; i < g.length; i++)
		    		System.out.println(((ALGOBuslineEdge)minEdges[i]).getBusline() + ": g = " + g[i] + ", h = " + h[i] + ", costs = " + minEdges[i].getCosts() + ", to = " + ((ALGOPlacemarkNode)getNode(minEdges[i].getSink())).getValue().getName());
			 */
		}
	}
	
    public BusNetTrip getOptimalTrip() {
    	return currentSolution;
    }
    
    public ALGOEdge getEdgeByLine(int source, String line) {
    	ALGOEdge [] edges = this.getEdgesForNode(source);
    	if (edges == null) return null;
    	else {
    		for (int i = 0; i < edges.length; i++) {
    			if (edges[i] instanceof ALGOBuslineEdge) {
    				ALGOBuslineEdge edge = (ALGOBuslineEdge)edges[i];
    				if (edge.getBusline().equals(line)) return edge;
    			}
    		}
    		
    		System.out.println("no edge found for line " + line);
    		return null;
    	}
    }
    
	
	public ALGOTrip computeBestPath(ALGOPlacemarkNode startNode, ALGOPlacemarkNode targetNode) {
		return computeShortestPath(startNode, targetNode);
	}
}
